package club.xiaojiawei.greedy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/27/22 11:12 AM
 * @question 1005. K 次取反后最大化的数组和
 * @description 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 */
public class LargestSumAfterKNegations1005 {

    public static void main(String[] args) {
        LargestSumAfterKNegations1005 test = new LargestSumAfterKNegations1005();
        int result = test.largestSumAfterKNegations2(new int[]{5,6,9,-3,3}, 2);
        System.out.println(result);
    }

    /**
     * 排序
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if(k > 0 ){
                if (nums[i] < 0){
                    k--;
                    count -= nums[i];
                }else if (k % 2 != 0){
                    k = 0;
                    if (i == 0){
                        count -= nums[i];
                        continue;
                    }
                    if (-nums[i - 1] < nums[i]){
                        count = count + (nums[i - 1] << 1) + nums[i];
                    }else {
                        count -= nums[i];
                    }
                }else {
                    count += nums[i];
                }
            }else {
                count += nums[i];
            }
        }
        if (k % 2 != 0){
            count = count + (nums[nums.length - 1] << 1);
        }
        return count;
    }

    /**
     * 民间-计数排序部分思想（nb）
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations2(int[] nums, int k) {
//        题目限定数的取值范围为-100~100,总共201个数
        int[] number = new int[201];
        int sum = 0;
//        遍历数组，统计每个数出现的次数
        for (int num : nums) {
//            num + 100的意思是将数值转换成下标
            number[num + 100]++;
        }
        int j = 0;
//        遍历找到所有负数
        while(k > 0){
//            找到出现次数非0的数
            while(number[j] == 0) j++;
//            如果该数大于0则结束遍历，即所有负数都找完了
            if(j >= 100) break;
            k--;
//            该数出现次数减1
            number[j]--;
//            该数的相反数出现次数加1（相当于该数取反）
            number[200 - j]++;
        }
//        如果k大于0则说明k大于负数的数量，且如果剩余次数为奇数的话找到最小的正数将它取反（如果剩余次数是偶数的话相当于不变）
        if(k > 0 && (k & 1) == 1) {
            number[j]--;
            number[200 - j]++;
        }
//        遍历求和
        for(int i = 0; i < number.length; i++){
            sum += number[i] * (i - 100);
        }
        return sum;
    }

    /**
     * 官方-从小到大修改每个负数
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations3(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int ans = Arrays.stream(nums).sum();
        for (int i = -100; i < 0; ++i) {
            if (freq.containsKey(i)) {
                int ops = Math.min(k, freq.get(i));
                ans += (-i) * ops * 2;
                freq.put(i, freq.get(i) - ops);
                freq.put(-i, freq.getOrDefault(-i, 0) + ops);
                k -= ops;
                if (k == 0) {
                    break;
                }
            }
        }
        if (k % 2 == 1 && !freq.containsKey(0)) {
            for (int i = 1; i <= 100; ++i) {
                if (freq.containsKey(i)) {
                    ans -= i * 2;
                    break;
                }
            }
        }
        return ans;
    }

    /**
     * 民间-双排序
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations4(int[] nums, int k) {
        // 排序，把可能有的负数排到前面
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 贪心：如果是负数，而k还有盈余，就把负数反过来
            if (nums[i] < 0 && k > 0) {
                nums[i] = -1 * nums[i];
                k--;
            }
            sum += nums[i];
        }
        Arrays.sort(nums);
        // 如果k没剩，那说明能转的负数都转正了，已经是最大和，返回sum
        // 如果k有剩，说明负数已经全部转正，所以如果k还剩偶数个就自己抵消掉，不用删减，如果k还剩奇数个就减掉2倍最小正数。
        return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
    }
}
